package leetcode.editor.cn;

import java.util.ArrayDeque;

/**
题目名字---:滑动窗口最大值
题目编号---:239	
解题时间---:2021-09-28 19:46:40
*/

public class SlidingWindowMaximum{
    public static void main(String[] args) {
        Solution solution = new SlidingWindowMaximum().new Solution();    
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        //初始化双端队列
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty()&&nums[i]<deque.getLast()) {
                deque.removeFirst();
            }
            deque.addLast(nums[i]);
        }

        for (int i = 1; i < nums.length - k; i++) {
            //?
            while (!deque.isEmpty()&&deque.getFirst() ==i-k) {
                deque.removeFirst();
            }

            while (!deque.isEmpty()&&nums[i]<deque.getLast()) {
                deque.removeFirst();
            }
            deque.addLast(nums[i]);
        }

        return null;
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        return null;
    }

}
//leetcode submit region end(Prohibit modification and deletion)


}